package JZOffer;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 剑指 Offer 07. 重建二叉树
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * **/

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
  }

class Solution07_1 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null||preorder.length == 0)
            return null;

        //第一步 获取根节点的value值
        TreeNode root = new TreeNode(preorder[0]);

        int index = findIndex(preorder, inorder);
        //第二步 构建left左子树 right 右子树
        root.left = buildTree(Arrays.copyOfRange(preorder, 1,index + 1),
                                Arrays.copyOfRange(inorder, 0, index));
        root.right = buildTree(Arrays.copyOfRange(preorder, index + 1, preorder.length),
                                Arrays.copyOfRange(inorder, index + 1, inorder.length));
        return root;
    }

    //构造一个找根的index函数
    public int findIndex(int[] preorder, int[] inorder){
        for (int i = 0; i<inorder.length; i++){
            if (inorder[i] == preorder[0]) return i;
        }
        return 0;
    }

}